package Algorithm.StackAndQueue;

import java.util.Arrays;
import java.util.Collections;
import java.util.Stack;

/**
 * @Author cj
 * @Date 2021/11/17 20:59
 */
public class getVisibleNum {

    public int getVisibleNum1(int[] arr) {
        int res = 0;
        // 找到最大值
        int maxIndex = 0;
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] > arr[maxIndex]) {
                maxIndex = i;
            }
        }
        // 单调栈
        Stack<Record> stack = new Stack<>();
        stack.push(new Record(arr[maxIndex]));
        int index = nextIndex(maxIndex, arr.length);
        while (index != maxIndex) {
             // 大于栈顶元素
            while (arr[index] > stack.peek().value) {
                int times = stack.pop().times;
                res += times == 1 ? 2 * times :
                        2 * times + times * (times - 1) / 2;
            }
            if (arr[index] == stack.peek().value) {
                stack.peek().times += 1;
            } else {
                stack.push(new Record(arr[index]));
            }
            index = nextIndex(index, arr.length);
        }
        /* 清算 */
        // 第一阶段
        while (stack.size() > 2) {
            int times = stack.pop().times;
            res += times == 1 ? 2 : 2 * times + (times * (times - 1) / 2);
        }
        // 第二阶段
        while (stack.size() > 1) {
            int times = stack.pop().times;
            res += times == 1 ? times + (times * (times - 1) / 2) :
                    2 * times + (times * (times - 1) / 2);
        }
        // 第三阶段
        if (stack.size() == 1) {
            int times = stack.pop().times;
            res += times == 1 ? 0 : times * (times - 1) / 2;
        }
        return res;
    }

    // 存放值和个数
    class Record {
        public int value;
        public int times;

        Record(int value) {
            this.value = value;
            this.times = 1;
        }
    }

    // 找数组下一个值，到最后反到头来找
    public static int nextIndex(int index, int size) {
        return index == size -  1 ? 0 : index + 1;
    }
}
